用一个栈实现另一个栈的排序

[编程题]用一个栈实现另一个栈的排序

热度指数：6257 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

输入描述:

第一行输入一个N，表示栈中元素的个数
第二行输入N个整数表示栈顶到栈底的各个元素

输出描述:

输出一行表示排序后的栈中栈顶到栈底的各个元素。

示例1

输入

5
5 8 4 3 6

输出

8 6 5 4 3

备注:

1 <= N <= 10000
-1000000 <=  <= 1000000

算法知识视频讲解

Python 3

火车长城长

python解法超时了

import sys

# 处理输入
N = sys.stdin.readline().strip()
stack = [int(i) for i in sys.stdin.readline().strip().split()]


# 使用辅助栈，基于汉诺塔原理实现栈的排序
def sortStack(stack):
    helper = []
    while stack:
        val = stack.pop()
        if not helper:
            helper.append(val)
        else:
            while helper and val > helper[-1]:
                stack.append(helper.pop())
            helper.append(val)
    while helper:
        stack.append(helper.pop())
    return stack

stack = sortStack(stack)
while stack:
    print(stack.pop(), end=' ')

发表于 2022-06-01 16:22:27 回复(0)